use std::collections::HashSet;

// 1. sum of n
pub fn sum_nums(n: i32) -> i32 {
    (n.pow(2) + n) >> 1
}

// 2. n is or isn't pow of 2
pub fn is_pow_of_two(n: i32) -> bool {
    return n > 0 && n&(n-1) == 0
}

// 3. the numbers of one in the unsigned number
pub fn hamming_weight(n: u32) -> u8 {
    let mut count: u8 = 0;
    let mask: u32 = 1;
    for i in 0..32 {
        if n&(mask << i) != 0 {
            count += 1;
        }
    }
    count
}
// 3.1
pub fn hamming_weight_v2(mut n: u32) -> u8 {
    let mut count: u8 = 0;
    while n > 0 {
        count += 1;
        n &= n-1;
    }
    count
}

// 4. the only one number 异或(2 bit)
pub fn single_number(nums: Vec<u32>) -> u32 {
    let mut res: u32 = 0;
    for num in nums {
        res ^= num;
    }
    res
}
// 4.1
pub fn single_number_v2(nums: Vec<u32>) -> u32 {
    let mut set: HashSet<u32> = HashSet::new();
    for i in 0..nums.len() {
        set.insert(nums[i]);
    }
    let set_sum = set.iter().sum::<u32>();
    let nums_sum = nums.iter().sum::<u32>();
    (set_sum*3 - nums_sum)/2
}
// 4.2 异或(3 bit)
pub fn single_number_v3(nums: Vec<u32>) -> u32 {
    let mut temp;
    let mut res: u32 = 0;
    for i in 0..32 {
        temp = 0;
        for j in 0..nums.len() {
            temp += nums[j] >> i & 1;
        }
        res |= temp%3 << i;
    }
    res
}
// 4.3
pub fn single_number_v4(nums: Vec<u32>) -> u32 {
    let mut a: u32 = 0;
    let mut b: u32 = 0;
    for n in nums {
        b = (b ^ n) & !a;
        a = (a ^ n) & !b;
    }
    b
}

// 5. 找出缺失的数字
pub fn missing_number(nums: Vec<u32>) -> u32 {
    let mut res: u32 = 0;
    let n = nums.len();
    for i in 0..n {
        res ^= i as u32 ^ nums[i];
    }
    res ^ n as u32
}